//
//  kmp_demo.hpp
//  cpp_algorithm
//
//  Created by 李贺 on 2022/1/13.
//  https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

#ifndef kmp_demo_hpp
#define kmp_demo_hpp

#include <stdio.h>
#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

namespace kmp_demo_space {

class Solution {
    
public:
    
    void get_next(int * next, const string &s) {
        int j = -1;
        next[0] = -1;
        string ss = s;
        for (int i = 1; i < s.size(); ++i) {
            while (j >= 0 && s[i] != ss[j + 1]) {
                j = next[j];
            }
            
            if (s[i] == ss[j+1]) {
                j++;
            }
            next[i] = j;
        }
    }
    
    int strStr(string haystack, string needle) {
            if (needle.size() == 0) {
                return 0;
            }
            int next[needle.size()];
            get_next(next, needle);
            int j = -1; // // 因为next数组里记录的起始位置为-1
            for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
                while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                    j = next[j]; // j 寻找之前匹配的位置
                }
                if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                    j++; // i的增加在for循环里
                }
                if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                    return (i - needle.size() + 1);
                }
            }
            return -1;
        }
};

class Solution1 {
    
public:
    // 前缀表:记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀
    // next 数组里存的是s[0...i] 的最大前后缀字符串长度
    // 是不断的回退前缀,去和后缀比较, i一直递增,j会回退
    // 想象成两个相同的字符串的前缀字符串和后缀字符串的匹配
    // j有两个作用, 1: 字符串ss的遍历位置,2记录最大公共前后缀的长度
    void getNext(int* next, const string& s) {
        int j = 0;
        // 开始这个肯定是0,
        next[0] = 0;
        const string ss = s;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != ss[j]) {
                
                j = next[j - 1];
            }
            
            if (s[i] == ss[j]) {
                j++;
            }
            
            next[i] = j;
        }
    }
    
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

}

#endif /* kmp_demo_hpp */
